Hình minh họa một ví dụ của thuật toán Gale-Shapley

Năm 1962, David Gale và Lloyd Shapley chứng minh rằng, với số lượng đàn ông và phụ nữ bằng nhau, luôn tồn tại lời giải bền vững cho SMP. Họ đưa ra một thuật toán để tìm lời giải đó.[2][3]

Thuật toán Gale-Shapley bao gồm nhiều "lượt" trong đó mỗi người đàn ông chưa đính hôn "cầu hôn" người phụ nữ anh ta thích nhất mà trước đó chưa cầu hôn. Mỗi phụ nữ xem xét tất cả mọi người cầu hôn và trả lời người cô thích nhất "có thể" và từ chối tất cả những người còn lại. Tạm thời cô được "đính hôn" với người đàn ông được cô chọn và anh ta cũng tạm thời "đính hôn" với cô. Như vậy trong lượt đầu tiên, đầu tiên a) mỗi người đàn ông cầu hôn người phụ nữ anh thích nhất, rồi b) mỗi người phụ nữ trả lời "có thể" với người cô thích nhất và từ chối tất cả những người khác. Ở những lượt tiếp theo, đầu tiên a) mỗi người đàn ông chưa đính hôn cầu hôn người phụ nữ anh ta thích nhất mà anh ta chưa cầu hôn trước đó (bất kể người đó có đang đính hôn hay không), sau đó b) mỗi người phụ nữ trả lời "có thể" với người cầu hôn cô thích nhất (bất kể đó là người đính hôn tạm thời hay người khác) và từ chối tất cả những người khác (có thể bao gồm cả người đính hôn tạm thời). Việc đính hôn tạm thời cho phép người phụ nữ đã đính hôn có thể tìm được người ngày càng tốt hơn ở những lượt về sau.

Thuật toán này đảm bảo rằng:

Tất cả mọi người đều được kết hônSau khi một phụ nữ đã đính hôn, cô luôn đính hôn với một người nào đó. Do đó cuối cùng không thể tồn tại một người đàn ông và một người phụ nữ đều chưa đính hôn vì anh ta nhất định cầu hôn với cô tại một thời điểm nào đó (vì một người đàn ông cuối cùng có thể cầu hôn với tất cả mọi phụ nữ nều cần thiết) và do cô chưa đính hôn, cô sẽ trả lời đồng ý.Hôn nhân bền vữngGiả sử Alice là một phụ nữ và Bob là một người đàn ông đều đã đính hôn, nhưng không đính hôn với nhau. Tại thời điểm thuật toán kết thúc, không thể xảy ra trường hợp cả Alice và Bob đều thích người kia hơn vợ/chồng của họ. Nếu Bob thích Alice hơn vợ anh ta, anh ta nhất định đã cầu hôn Alice trước khi cầu hôn vợ mình. Nếu Alice chấp nhận lời cầu hôn đó nhưng cuối cùng không kết hôn với Bob, cô nhất định bỏ anh ta theo một người khác cô thích hơn. Nếu Alice từ chối lời cầu hôn, cô nhất định đã đính hôn với người cô thích hơn Bob.